package leetcode.code1463;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int m, n;

	int[][] grid;

	public int cherryPickup(int[][] grid) {
		m = grid.length;
		n = grid[0].length;
		Integer[][][] dp = new Integer[m][n][n];
		this.grid = grid;
		return f(0, 0, n - 1, dp);
	}

	int[] d = new int[] { -1, 0, 1 };

	private int f(int i, int j, int l, Integer[][][] dp) {
		if (i == m || j < 0 || j == n || l < 0 || l == n) {
			return 0;
		}
		if (dp[i][j][l] != null) {
			return dp[i][j][l];
		}
		int cur = grid[i][j] + (j == l ? 0 : grid[i][l]);
		int max = 0;
		for (int p = 0; p < 3; p++) {
			for (int q = 0; q < 3; q++) {
				max = Math.max(max, f(i + 1, j + d[p], l + d[q], dp));
			}
		}
		dp[i][j][l] = cur + max;
		return cur + max;
	}

	@Override
	public void debug4() {
		H.compare(24, this.cherryPickup(H.str2array1("[[3,1,1],[2,5,1],[1,5,5],[2,1,1]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
